package com.linyaonan.leetcode.medium._2982;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 给你一个仅由小写英文字母组成的字符串 s 。
 *
 * 如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
 *
 * 返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。
 *
 * 子字符串 是字符串中的一个连续 非空 字符序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "aaaa"
 * 输出：2
 * 解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。
 * 可以证明最大长度是 2 。
 * 示例 2：
 *
 * 输入：s = "abcdef"
 * 输出：-1
 * 解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。
 * 示例 3：
 *
 * 输入：s = "abcaba"
 * 输出：1
 * 解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。
 * 可以证明最大长度是 1 。
 *
 *
 * 提示：
 *
 * 3 <= s.length <= 5 * 10^5
 * s 仅由小写英文字母组成。
 *
 * @author: Lin
 * @date: 2024/12/12
 */
public class FindLongestSpecialSubstringThatOccursThriceII {

    /**
     * 首先全部由小写字母组成，那么使用数组int[26]来管理，然后每一个会存在重复的字串，将字串的长度记录在列表中
     * 组成的数据结构为 List<List<Integer>> 的结构
     * @param s
     * @return
     */
    public int maximumLength(String s) {
        boolean hashHead = false;
        char head = '1';
        int l = 0;
        List<Queue<Integer>> lists = new ArrayList<>(26);
        // 初始化
        for (int i = 0; i < 26; i++) {
            lists.add(new PriorityQueue<>(3, Comparator.comparingInt(i2 -> i2)));
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!hashHead) {
                head = c;
                l = 1;
                hashHead = true;
            } else {
                if (c == head) {
                    l++;
                } else {
                    Queue<Integer> queue = lists.get(head - 'a');
                    if (queue.size() == 3) {
                        queue.remove();
                    }
                    lists.get(head - 'a').add(l);
                    l = 1;
                    head = c;
                }
            }
        }
        // 最后一组数据
        {
            Queue<Integer> queue = lists.get(head - 'a');
            if (queue.size() == 3) {
                queue.remove();
            }
            lists.get(head - 'a').add(l);
        }

        System.out.println(lists);
        return check(lists);
    }

    public int check(List<Queue<Integer>> org) {
        int max = -1;
        for (int i = 0; i < org.size(); i++) {
            Queue<Integer> list = org.get(i);
            // 已经找到三组情况
            if (list.size() == 3) {
                // 取出三个元素
                int _temp3 = list.remove();
                int _temp2 = list.remove();
                int _temp1 = list.remove();
                {
                    // 1. 情况一 三个全部组成，取最小
                    int _tempMin = Math.min(Math.min(_temp1, _temp2), _temp3);
                    max = Math.max(max, _tempMin);
                }
                {
                    // 2. 情况二 前两个组成
                    // 2.1 两个相等
                    if (_temp1 == _temp2) {
                        max = Math.max(max, _temp1 - 1);
                    } else {
                        max = Math.max(max, (Math.min(_temp1 - 1, _temp2)));
                    }

                }
                {
                    // 3. 情况三 第一个组成
                    max = Math.max(max, _temp1 - 2);
                }
            } else {
                // 0组
                if (list.isEmpty()) {
                    continue;
                }
                int size = list.size();
                if (size == 1) {
                    int _temp = list.remove();
                    if (_temp > 2) {
                        // 找到最大的 - 2
                        max = Math.max(_temp - 2, max);
                    }
                } else {
                    // 两组
                    // aaaaa aaaa
                    int _temp2 = list.remove();
                    int _temp1 = list.remove();
                    // 两个单独元素
                    if (_temp2 == _temp1 && _temp1 == 1) {
                        continue;
                    }
                    // 多种情况
                    // 1. 单独由前一组组成三组
                    {
                        int temp = _temp1 - 2;
                        max = Math.max(max, temp);
                    }
                    {
                        // 2. 前面两组，后面一组
                        int temp = _temp1 - 1;
                        max = Math.max(Math.min(temp, _temp2), max);
                    }
                }
            }
        }

        return max;
    }

}
